import java.util.ArrayList;
import java.util.List;

public class num93 {
    List<String> list = new ArrayList<>();
    StringBuilder sb = new StringBuilder();
    public List<String> restoreIpAddresses(String s) {
        dfs(new StringBuilder(s),0,0);
        return list;
    }

    private void dfs(StringBuilder s, int start, int cnt) {
        if(start == s.length() && cnt == 4) {
            list.add(sb.toString());
            return;
        }
        if(start == s.length() || cnt == 4) {
            return;
        }
        for (int i = start; i < s.length(); i++) {
            if(i == start + 3) {
                return;
            }
            if(i > start && s.charAt(start) == '0') {
                return;
            }
            String tem = s.substring(start,i + 1);
            int val = Integer.parseInt(tem);
            if(val > 255 || val < 0) {
                return;
            }
            sb.append(tem);
            if(cnt < 3) {
                sb.append(".");
            }
            dfs(s,i + 1,cnt + 1);
            sb.delete(start + cnt,sb.length());
        }
    }
}
